class Solution {
public:

    void backtrack(vector<string>& results, string& one_res, int n, int start_id) {
      static char parenthesis[2] = {'(', ')'};
      static vector<char> parenthesis_list{')'};

      if(one_res.size() == n*2){
        results.push_back(one_res);
        return;
      }

      for(int i = 0; i < 2; i++){
        if(one_res.size() + parenthesis_list.size() == n*2){
          if(i != 1) continue;
        }
        else if(parenthesis_list.size() == 0){
          if(i != 0) continue;
        }
        one_res.push_back(parenthesis[i]);
        if(parenthesis[i] == '(') parenthesis_list.push_back(parenthesis[i]);
        else parenthesis_list.pop_back();
        backtrack(results, one_res, n, start_id + 1);
        one_res.pop_back();
      }
    }

    vector<string> generateParenthesis(int n) {

      vector<string> results;
      string res("(");
      backtrack(results, res, n, 1);

      return results;
    }
};